public class MergeTwoLists {
    //迭代
    public static Node mergeTwoLists(Node head1, Node head2) {
        Node newNode = new Node(0);//虚拟节点,数据没有意义
        Node temp = newNode;
        while(head1!=null&&head2!=null){
            if(head1.val< head2.val){
                temp.next = head1;
                temp = temp.next;
                head1 = head1.next;
            }else{
                temp.next = head2;
                temp = temp.next;
                head2 = head2.next;
            }
        }
        if(head1!=null){
            temp.next = head1;
        }
        if(head2!=null){
            temp.next = head2;
        }
        return newNode.next;
    }
    //递归
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null||l2==null){
            return l1!=null?l1:l2;
        }
        if(l1.val<=l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.addLast(12);
        singleLinkedList1.addLast(20);
        singleLinkedList1.addLast(25);
        singleLinkedList1.addLast(30);
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.addLast(12);
        singleLinkedList2.addLast(18);
        singleLinkedList2.addLast(26);
        singleLinkedList2.addLast(28);
        Node ret = mergeTwoLists(singleLinkedList1.head,singleLinkedList2.head);
        singleLinkedList1.myToString(ret);
    }
}
